1. Field of the Invention
This invention relates to computer systems and, more particularly, to methods and apparatus for improving the speed of operations of a computer system by means of improved caching arrangements.
2. History of the Prior Art
A typical general purpose computer comprises among other elements a central processing unit which operates under program instruction to accomplish control, logic, and arithmetic functions; a main memory usually made up of random access memory in which instructions and data are stored for use by the central processing unit; supplemental long term memory; input/output control apparatus for moving information between the outside world and the computer; and some arrangement for displaying the results of operations such as a display monitor. Computers operate through their central processing units by storing programs (sets of instructions) and data in memory and selectively retrieving those instructions and data to the central processing unit for manipulation.
Computers become more capable by increasing the speed of operation and the amount and complexity of the information they can handle. The main way in which this is accomplished is by making the central processing units and memory faster and the memory space larger. Unfortunately, more memory is more expensive and faster memory is much more expensive. Consequently, caching arrangements have evolved. A cache is a relatively small amount of high speed memory used between the central processing unit and the main memory in a computer system to improve the speed of operation of the system by storing those instructions and that data which is used most often in a program. A correctly designed caching arrangement will usually contain (over ninety percent of the time) the information sought by the central processing unit. Thus, the central processing unit is usually operating with the faster cache memory, and the overall speed of operation of the system increases.
There have been many different caching arrangements designed to increase the speed of operation of computer systems. Typically, a cache memory utilizes an associated tag memory in which the main memory addresses of information stored in the cache are kept. When a request is directed to memory for information at a particular address, the address is compared with the addresses in the tag memory. If the address resides in the tag memory, the information is accessed from the cache memory; if not, then main memory is accessed for the information. The tag memory, though small, is very expensive.
It is typical for a cache memory to receive a small amount such as thirty-two bytes of information in each access of main memory. The time required to transfer such a small amount of information is relatively insignificant. However, a cache can be designed to receive information at higher rates, for example, in blocks of one, two, or four kilobytes at a time. The time required to accomplish a transfer from main memory with such a cache, is relatively significant in the overall system operation. Moreover, when there is a miss (the information is unavailable) in a cache memory, then the central processing unit must move the information from main memory to the cache memory and then access the information in the cache for use. This process of transferring the information takes a substantial amount of time in a system which fills the cache in large increments.